import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-07-20
 * Time: 22:41
 */

public class Solution {
    public long maxScore(int[] nums1, int[] nums2, int k) {
        long res = 0L;
        int n = nums1.length;

        // 数组 nums2 按降序排列后的下标。
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; ++i) ids[i] = i;
        // 这样排序的话, 相当于同时将数组 1 和 2 同步进行排序了
        Arrays.sort(ids, (i, j) -> nums2[j] - nums2[i]);

//         接下来的思路就是, 在某个值为最小值的情况下, 选择 k 个最大的值
//         但是这个值最小是前提, 所以这 k 个数也得选择 比这个值大的下标对应的值

        // nums1 的前 k - 1 个值的和
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // 小根堆
        long sum1 = 0L;
        // 这样选出来的值, 都是在 某个值是最小值的前提下
        for (int i = 0; i < k - 1; ++i) {
            int id = ids[i];
            sum1 += nums1[id];
            minHeap.offer(nums1[id]);
        }

        // 从第 k 个元素（下标 k - 1）开始计算
        for (int i = k - 1; i < n; ++i) {
            int id = ids[i];
            int num1 = nums1[id];
            // 1. 加上 num1，构成 k 个数
            sum1 += num1;
            minHeap.offer(num1);
            // 2. 比较
            res = Math.max(sum1 * nums2[id], res);
            // 3. 删除 k 个数中最小的数
            // 为什么删除最小的就行, 而不是指定的某个呢
            // 因为只要保证了 nums2[id] 是最小值就行, 然后再选出来 k 个最大的值即可
            sum1 -= minHeap.poll();
        }

        return res;
    }
}
